import Dictionary from "./Dictionary";
import { Queue } from "./Queue";

/**
 * 图
 * 广度优先搜索 BFS
 * 深度优先搜索 DFS
 * 为保证算法的效率 每个顶点最多访问两次
 * 使用三种颜色反映顶点状态 白色 未访问 灰色 访问但未探索 黑色 被访问且被完全探索
 */
export class Graph{
    isDirected = false;
    vertices:any[] = [];
    adjList = new Dictionary()
    constructor(isDirected = false){
        this.isDirected = isDirected;
    }
    /**
     * 添加顶点
     * @param v 
     */
    addVertex(v:any){
        if(!this.vertices.includes(v)){
            this.vertices.push(v);
            this.adjList.insert(v,[]);
        }
    }
    /**
     * 连接两个顶点
     * @param v 
     * @param w 
     */
    addEdge(v:any,w:any){
        if(!this.adjList.has(v)){
            this.addVertex(v);
        }
        if(!this.adjList.has(w)){
            this.addVertex(w);
        }
        this.adjList.get(v).push(w);
        //无向 两个顶点互相连接
        if(!this.isDirected){
            this.adjList.get(w).push(v);
        }
    }
    getVertices(){
        return this.vertices;
    }
    getAdjList(){
        return this.adjList;
    }
    toString(){
        let s = "";
        for(let i = 0;i<this.vertices.length;i++){
            s+=`${this.vertices[i]} -> `;
            const neighbors = this.adjList.get(this.vertices[i]);
            for(let j = 0 ;j<neighbors.length;j++){
                s+=`${neighbors[j]} `;
            }
            s+='\n'
        }
        return s;
    }
}
const Colors = {
    WHITE:0,
    GREY:1,
    BLACK:2
}
const initializeColor = (vertices:any[]) =>{
    const color:{
        [k:string]:any
    } = {};
    for(let i = 0;i<vertices.length;i++){
        color[vertices[i]] = Colors.WHITE;
    }
    return color;
}
const breadthFirstSearch = (graph:Graph,startVertex:any,callback:(a:any)=>void)=>{
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color:any = initializeColor(vertices);
    const queue = new Queue();
    queue.enqueue(startVertex);
    while(!queue.isEmpty()){
        const u:any = queue.dequeue();
        const neighbors = adjList.get(u);
        color[u] = Colors.GREY; 
        for(let i = 0;i<neighbors.length;i++){
            let w = neighbors[i];
            if(color[w] === Colors.WHITE){
                color[w] = Colors.GREY;
                queue.enqueue(w)
            }
        }
        color[u] = Colors.BLACK;
        if(callback){
            callback(u);
        }
    }
}
/**
 * 广度优先遍历
 * @param graph 
 * @param startVertex 
 * @returns startVertex 到各个顶点的距离，和前溯点
 */
const BFS = (graph:Graph,startVertex:any)=>{
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color:any = initializeColor(vertices);
    const queue:Queue<string> = new Queue();
    const distances:any = {};
    const predecessors:any = {};
    queue.enqueue(startVertex);

    for(let i = 0;i<vertices.length;i++){
        distances[vertices[i]] = 0;
        predecessors[vertices[i]] = null;
    }

    while(!queue.isEmpty()){
        const u:string = queue.dequeue();
        const neighbors = adjList.get(u);
        color[u] = Colors.GREY;
        for(let i = 0;i<neighbors.length;i++){
            const w = neighbors[i]
            if(color[w] === Colors.WHITE){
                color[w] = Colors.GREY;
                distances[w] = distances[u] + 1;
                predecessors[w] = u;
                queue.enqueue(w);
            }
        }
        color[u] = Colors.BLACK;
    }
    return {
        distances,
        predecessors
    }
}
/**
 * BFS 返回结果输出为string
 */
const BFS2String = (myVertices:any[],predecessors:any)=>{
    const fromVertex = myVertices[0];
    for(let i = 0;i<myVertices.length;i++){
        const toVertex = myVertices[i];
        const path = [];
        for(let v = toVertex;
            v !== fromVertex;
            v = predecessors[fromVertex]
            ){
            path.push(v);
        }
        path.push(fromVertex);
        let s = path.pop();
        while(path.length){
            s += " - " + path.pop();
        }
        console.log(s);
    }
}

const DFS = function(graph:Graph){
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);

    let d:any = {};//发现时间
    let f:any = {};//完成探索时间
    let p:any = {};//前溯点
    const time = {count:0}

    for(let i = 0;i<vertices.length;i++){
        f[vertices[i]] = 0;
        d[vertices[i]] = 0;
        p[vertices[i]] = null;
    }
    for(let i = 0;i<vertices.length;i++){
        if(color[vertices[i]] === Colors.WHITE){
            DFSVisit(vertices[i],color,d,f,p,time,adjList)
        }
    }

    function DFSVisit(u:any,color:any,d:any,f:any,p:any,time:any,adjList:any){
        color[u] = Colors.GREY;
        d[u] = ++time.count;
        const neighbors = adjList.get(u)
        for(let i = 0;i<neighbors.length;i++){
            let w = neighbors[i];
            if(color[w] === Colors.WHITE){
                p[w] = u;
                DFSVisit(w,color,d,f,p,time,adjList);
            }
        }
        color[u] = Colors.BLACK;
        f[u] = ++time.count;
    }
    

}